今天是紀錄LeetCode解題的第二十天

第二十題題目：Given a string s containing just the characters ' ( ', ' ) ', ' { ', ' } ', ' [ ' and ' ] ', determine if the input string is valid.
An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.

給定一個字串s僅包含字元' ( ', ' ) ', ' { ', ' } ', ' [ ' 和 ' ] '，確定輸入字串是否有效
如果滿足以下條件，則字串有效:

• 每個左括號需有相同類型的括號閉合
• 括號必須按照正確的順序閉合
• 每個右括號都有與之對應的同類型的左括號

解題思路

這題的概念非常簡單，我們只要遇到左括號，直接放進堆疊，遇到右括號的話，先檢查堆疊裡有沒有元素，如果堆疊是空的，表示一開始就遇到右括號或左括號數量不足無法完全對應，那就直接回傳False，如果堆疊不為空，檢查堆疊裡的最後一個元素是不是與之對應的左括號，如果對應到的話就直接pop出來，反之一樣回傳False，最後我們還要檢查堆疊是否為空來確認所有括號是否都對應完畢

程式碼如下

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in "({[":
                stack.append(c)
            elif c == ")":
                if not stack or stack[-1] != "(": #如果堆疊是空的表示一開始遇到右括號或左括號數量不足，或是最後一個不是對應的右括號
                    return False
                stack.pop() #如果對應到就取出來
            elif c == "}":
                if not stack or stack[-1] != "{":
                    return False
                stack.pop()
            elif c == "]":
                if not stack or stack[-1] != "[":
                    return False
                stack.pop()
        return not stack #最後回傳是不是空堆疊，是的話代表每個括號都配對到則回傳True，反之

執行過程

初始狀態

• s = "( [ ] )"
• stack = []

第一次執行(c = ' ( ')

• stack.append(' ( ') → stack = [' ( ']

第二次執行(c = ' [ ')

• stack.append(' [ ') → stack = [' ( ' , ' [ ']

第三次執行(c = ' ] ')

• if not stack or stack[-1] != " [ " → False
• stack.pop() → stack = [' ( ']

第四次執行(c = ' ) ')

• if not stack or stack[-1] != " ) " → False
• stack.pop() → stack = []

結果

• return not stack → return True